package main.leetcode.clockin.May;

/**
 * 221.最大正方形
 *
 * <p>在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximal-square
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day8 {
    public static void main(String[] args) {
        System.out.println(
                new day8()
                        .maximalSquare(
                                new char[][] {
                                    {1, 0, 1, 0, 0},
                                    {1, 0, 1, 1, 1},
                                    {1, 1, 1, 1, 1},
                                    {1, 0, 0, 1, 0}
                                }));
    }

    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
                    res = Math.max(res, dp[i + 1][j + 1]);
                }
            }
        }
        return res * res;
    }
}
